package com.xzz.backtrack;

/**
 * @author: hhz
 * @create: 2022-01-11 14:41
 * 698. 划分为k个相等的子集
 **/
public class CanPartitionKSubsets {
    public static void main(String[] args) {
        System.out.println(canPartitionKSubsets(new int[]{4,3,2,3,5,2,1},4));
    }
    public static boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum+=num;
        }
        if(sum%k!=0){
            return false;
        }
        int target = sum/4;
        return backtrack(nums, k, target, 0, new boolean[nums.length], 0);
    }

    public static boolean backtrack(int[] nums, int k,int target,int start,boolean[] used,int curSum) {
        if(k==0){
            return true;
        }
        if(curSum==target){
            return backtrack(nums,k-1,target,0,used,0);
        }

        for (int i = start; i < nums.length; i++) {
            if(used[i]){
                continue;
            }
            int curNum = nums[i];
            if(curSum+curNum>target){
                continue;
            }
            curSum+=curNum;
            used[i]=true;

            if (backtrack(nums, k , target, i + 1, used, curSum)) {
                return true;
            }


            curSum-=curNum;
            used[i]=false;

        }

        return false;
    }
}
